{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Numbers With Repeated Digits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numDupDigitsAtMostN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #至少有 1 位重复的数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定正整数&nbsp;<code>n</code>，返回在<em>&nbsp;</em><code>[1, n]</code><em>&nbsp;</em>范围内具有 <strong>至少 1 位</strong> 重复数字的正整数的个数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 20\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>具有至少 1 位重复数字的正数（&lt;= 20）只有 11 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 100\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>具有至少 1 位重复数字的正数（&lt;= 100）有 11，22，33，44，55，66，77，88，99 和 100 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1000\n",
    "<strong>输出：</strong>262\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [numbers-with-repeated-digits](https://leetcode.cn/problems/numbers-with-repeated-digits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [numbers-with-repeated-digits](https://leetcode.cn/problems/numbers-with-repeated-digits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['20', '100', '1000']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        sn = str(n)\n",
    "        ln = list(int(x) for x in sn)\n",
    "        m = len(sn)\n",
    "        for i in range(1,m):\n",
    "            if ln[i] in ln[:i]:\n",
    "                while ln[i] in ln[:i]:\n",
    "                    ln[i]-=1\n",
    "                if ln[i]==-1:\n",
    "                    ln[i]=0\n",
    "                    for j in range(i+1,m):\n",
    "                        ln[j]=0\n",
    "                else:\n",
    "                    mh=9\n",
    "                    for j in range(i+1,m):\n",
    "                        while mh in ln[:j]:\n",
    "                            mh-=1\n",
    "                        ln[j]=mh\n",
    "                break\n",
    "\n",
    "        if m == 1:\n",
    "            return 0\n",
    "        diff = 0\n",
    "\n",
    "        for b in range(1, m):\n",
    "            # 从十个数字中选b个不同的  减去第一个数字如果选0那么就不是b位数了。\n",
    "            # 第一个数字选零 后面b-1 就是从9个数字里面选b-1\n",
    "            # dcnt[b]=perm(10,b)-perm(9,b-1)\n",
    "            diff +=  math.perm(10, b) -  math.perm(9, b - 1)\n",
    "        # 有m位的时候\n",
    "        ppick=[]\n",
    "        for i in range(0, m):\n",
    "            pre = i + 1\n",
    "            left = m - pre\n",
    "            if i == 0:\n",
    "                # 不能选0\n",
    "                hn = ln[0] - 1\n",
    "                diff += hn *  math.perm(9, left)\n",
    "            elif i==m-1:\n",
    "                for j in range(ln[i]+1):\n",
    "                    if j not in ln[:i]:\n",
    "                        diff+=1\n",
    "            else:\n",
    "                dup=True\n",
    "                for j in range(ln[i]):\n",
    "                    if j not in ln[:i]:\n",
    "                        dup=False\n",
    "                        diff += math.perm(10 - pre, left)\n",
    "                if dup:\n",
    "                    if ln[i] in ln[:i]:\n",
    "                        break\n",
    "\n",
    "        return n - diff\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        @lru_cache\n",
    "        def func(i: int, mask: int, is_limit: bool, is_num: bool) -> int: \n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            \n",
    "            res = 0 \n",
    "            \n",
    "            if is_num == False:\n",
    "                res += func(i+1, mask, False, False)\n",
    "            \n",
    "            max_d = int(s[i]) if is_limit else 9\n",
    "            low_d = 0 if is_num else 1\n",
    "            for d in range(low_d, max_d + 1):\n",
    "                if (mask >> d & 1) > 0:\n",
    "                    continue \n",
    "\n",
    "\n",
    "                mask = mask | (1 << d)\n",
    "                res += func(\n",
    "                    i+1, \n",
    "                    mask, \n",
    "                    is_limit and (d == max_d), \n",
    "                    True\n",
    "                )\n",
    "                mask = mask ^ (1 << d)\n",
    "            \n",
    "            return res \n",
    "        \n",
    "        return n - func(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        if n<10:\n",
    "            return 0\n",
    "        s=str(n)\n",
    "        l=len(s)\n",
    "        for i in range(l-1):\n",
    "            f=9\n",
    "            for j in range(i):\n",
    "                f*=(9-j)\n",
    "            #print(f)\n",
    "            n-=f\n",
    "        @cache\n",
    "        def find(x,u,ss):\n",
    "            if x==l:\n",
    "                return 1\n",
    "            tp= int(s[x]) if u else 9\n",
    "            tpp=0\n",
    "            for i in range(tp+1):\n",
    "                if x==0 and i==0:\n",
    "                    continue\n",
    "                if ss[i]=='1':\n",
    "                    continue\n",
    "                sss=list(ss)\n",
    "                sss[i]='1'\n",
    "                ss=\"\".join(sss)\n",
    "                #print(x+1,u and i==int(s[x]),ss)\n",
    "                tpp+=find(x+1,u and i==int(s[x]),ss)\n",
    "                sss[i]='0'\n",
    "                ss=\"\".join(sss)\n",
    "            return tpp\n",
    "        n-=find(0,True,\"0000000000\")\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        def countSpecialNumbers(n: int) -> int:\n",
    "            s = str(n)\n",
    "            m = len(s)\n",
    "\n",
    "            f = [[-1] * (1 << 10) for _ in range(m)]\n",
    "\n",
    "            def dfs(i: int, mask: int, is_limit: bool, is_num: bool) -> int:\n",
    "                if i == m:\n",
    "                    return is_num\n",
    "                \n",
    "                if not is_limit and is_num and f[i][mask] >= 0:\n",
    "                    return f[i][mask]\n",
    "\n",
    "                res = 0\n",
    "                if not is_num:\n",
    "                    res += dfs(i + 1, mask, False, False)\n",
    "                up = 9 if not is_limit else (ord(s[i]) - ord('0'))\n",
    "                for d in range(1 - is_num, up + 1):\n",
    "                    if (mask >> d & 1) == 0:\n",
    "                        res += dfs(i + 1, mask | (1 << d), is_limit and d == up, True)\n",
    "                \n",
    "                if not is_limit and is_num:\n",
    "                    f[i][mask] = res\n",
    "                return res\n",
    "\n",
    "            return dfs(0, 0, True, False)\n",
    "        \n",
    "        return n - countSpecialNumbers(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        digits = list(map(int, str(n)))\n",
    "        m = len(digits)\n",
    "        memo = [[-1] * 1024 for _ in range(m)]\n",
    "\n",
    "        def f(i, mask, lim):\n",
    "            if i == m:\n",
    "                return int(mask != 0)\n",
    "            if not lim and memo[i][mask] != -1:\n",
    "                return memo[i][mask]\n",
    "            res = 0\n",
    "            hid = digits[i] if lim else 9\n",
    "            for d in range(hid+1):\n",
    "                if not mask >> d & 1:\n",
    "                    res += f(i+1, mask | ((1 << d) if mask != 0 or d != 0 else 0), lim and d == hid)\n",
    "            if not lim:\n",
    "                memo[i][mask] = res\n",
    "            return res\n",
    "\n",
    "        return n - f(0, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        digit = [int(d) for d in reversed(list(str(n)))]\n",
    "        length = len(digit)\n",
    "        dp = [[-1 for j in range(1<<10)] for i in range(length)]\n",
    "\n",
    "        def dfs(idx: int, tight: bool, mask: int, lead: bool) -> int:\n",
    "            if idx < 0: return 1 if not lead else 0\n",
    "            if dp[idx][mask] != -1 and not tight and not lead:\n",
    "                return dp[idx][mask]\n",
    "            ret, sup = 0, digit[idx] if tight else 9\n",
    "            for i in range(sup + 1):\n",
    "                if mask & (1 << i): continue\n",
    "                newLead = lead and i == 0\n",
    "                newMask = mask if newLead else mask | (1 << i)\n",
    "                ret += dfs(idx-1, tight and i == digit[idx], newMask, newLead)\n",
    "            if dp[idx][mask] == -1 and not tight and not lead:\n",
    "                dp[idx][mask] = ret\n",
    "            return ret\n",
    "\n",
    "        return n - dfs(length - 1, True, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        @cache\n",
    "        def num_dp(s: str, i: int, mask: int, is_limit: bool, is_num: bool) -> int:\n",
    "            # i 越界 表示遍历完毕\n",
    "            if i == len(s):\n",
    "                # 如果 is_num 为真，则数字合法(全部填了数字)返回 1；否则返回 0 \n",
    "                return int(is_num)\n",
    "            res = 0     # 结果初始化为 0\n",
    "            # is_num 为假 可以跳过当前数位\n",
    "            if not is_num:\n",
    "                # res 加上跳过当前数位的结果\n",
    "                res += num_dp(s, i + 1, mask, False, False)\n",
    "            low = 0 if is_num else 1    # 当前填的数字的下界 如果前面为填过数字则为 1；否则为 0 (因为没有前导 0 )\n",
    "            high = int(s[i]) if is_limit else 9    # 当前填的数字的上界 如果被 s 限制则为 s[i]；否则为 9\n",
    "            for j in range(low, high + 1):\n",
    "                if (mask >> j & 1) == 0:    # j 不在 mask 中\n",
    "                    # mask 要加上当前的数字\n",
    "                    # 当当前位被限制且 j 到达上界后才将 is_limit 设为 True\n",
    "                    # 由于已经填了数字 is_num 为 True\n",
    "                    res += num_dp(s, i + 1, mask | (1 << j), is_limit and j == high, True)\n",
    "            return res\n",
    "        return n - num_dp(str(n), 0, 0, 1, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        #返回所有数位都不同的数字的个数，mask表示已选数字的掩码\n",
    "        @cache\n",
    "        def f(indx, limit, mask):\n",
    "            if indx == -1:\n",
    "                return 1 if mask > 0 else 0\n",
    "            res, k = 0, n//(10**indx)%10 #第indx位的数字\n",
    "            for i in range(k+1 if limit else 10):\n",
    "                if (1<<i)&mask > 0:\n",
    "                    continue\n",
    "                res += f(indx - 1, limit and i == k,mask if i==0 and mask == 0 else mask|(1<<i) )\n",
    "            return res\n",
    "        return n-f(len(str(n))-1, True, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        \n",
    "        @cache\n",
    "        def f(i,mask,is_limit,is_num):\n",
    "            if i == len(s):\n",
    "                return int(is_num)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1,mask,False,False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for d in range(1-is_num,up+1):\n",
    "                if mask & (1<<d)==0:\n",
    "                    res += f(i+1,mask|(1<<d),is_limit and up==d,True)\n",
    "            return res\n",
    "        return n-f(0,0,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i:int,is_limit:bool,is_num:bool,mask:int)->int:\n",
    "            if i == len(s):\n",
    "                return 1\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += f(i+1,False,False,mask)\n",
    "            low = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for j in range(low, up+1):\n",
    "                if (mask >> j) & 1:\n",
    "                    continue\n",
    "                res += f(i+1,is_limit and j == up, True, mask | (1 << j))\n",
    "            return res\n",
    "        # 这里求的是0-n不含有重复的数字，所以需要先减去1\n",
    "        # n - (f(0,True,False,0) - 1)\n",
    "        return  n - f(0,True,False,0)+1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "\n",
    "        def num_dp(l, r, condition, change, endCondition, start_state):\n",
    "\n",
    "            @cache\n",
    "            def f(n: int, s: str, inx: int=0, is_limit: bool=True, is_num: bool=False, state: int=0) -> int:\n",
    "                if inx == len(s):\n",
    "                    return int(is_num and endCondition(n, state))\n",
    "                res = f(n, s, inx + 1, False, False, state) if not is_num else 0\n",
    "                l = 0 if is_num else 1\n",
    "                r = int(s[inx]) if is_limit else 9\n",
    "                for i in range(l, r + 1):\n",
    "                    if condition(n, inx, i, state):\n",
    "                        res += f(n, s, inx + 1, is_limit and i == r, True, change(n, inx, i, state))\n",
    "                return res\n",
    "\n",
    "            return f(r, str(r), state=start_state(r))-f(l-1, str(l-1), state=start_state(l-1))\n",
    "\n",
    "        def condition(n, inx, val, state):\n",
    "            return state >> val & 1 == 0\n",
    "\n",
    "        def change(n, inx, val, state):\n",
    "            return state | (1 << val)\n",
    "\n",
    "        def end_condition(n, state):\n",
    "            return True\n",
    "\n",
    "        def start_state(n):\n",
    "            return 0\n",
    "\n",
    "        return n-num_dp(1, n, condition, change, end_condition, start_state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, N: int) -> int:\n",
    "        self.length = 0\n",
    "        self.nums = [0]\n",
    "        while N:\n",
    "            self.length += 1\n",
    "            self.nums.append(N % 10)\n",
    "            N //= 10\n",
    "        self.dp = [[[-1 for _ in range(2)] for _ in range(1024)] for _ in range(self.length + 1)]\n",
    "        \n",
    "        def dfs(pos, state, succ, lead, flag):\n",
    "            # finish enum the last digit\n",
    "            if pos == 0:\n",
    "                return succ\n",
    "            if not flag and not lead and self.dp[pos][state][succ] != -1:\n",
    "                return self.dp[pos][state][succ]\n",
    "            # search upper bound\n",
    "            limit = self.nums[pos] if flag else 9\n",
    "            # search lower bound\n",
    "            start = 1 if lead else 0\n",
    "            res = 0\n",
    "            for i in range(start, limit + 1):\n",
    "                res += dfs(pos - 1, state|(1<<i), succ|((state>>i)&1), False, (flag and i==limit))\n",
    "            if not flag and not lead:\n",
    "                self.dp[pos][state][succ] = res\n",
    "            return res\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(self.length, 0, -1):\n",
    "            ans += dfs(i, 0, 0, True, i==self.length);\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        l = len(n)\n",
    "        v = list(map(int, list(n)))\n",
    "        c = [0] * 10\n",
    "        @lru_cache(maxsize=1000000)\n",
    "        def dp(i, z, u, has, tc):\n",
    "            if i == l:\n",
    "                return has\n",
    "            cr = 0\n",
    "            for j in range(10):\n",
    "                if u and j > v[i]:\n",
    "                    break\n",
    "                if z and j == 0:\n",
    "                    cr += dp(i + 1, 1, 0, 0, tuple(c))\n",
    "                else:\n",
    "                    c[j] += 1\n",
    "                    cr += dp(i + 1, 0, int(u == 1 and j == v[i]), has | int(c[j] > 1), tuple(c))\n",
    "                    c[j] -= 1\n",
    "            return cr\n",
    "\n",
    "        # res1 = dp(0, 1, 1, 0, tuple(c))\n",
    "        @lru_cache(maxsize=100000)\n",
    "        def dp1(i, z, u, mask):\n",
    "            if i == l:\n",
    "                return 1 ^ z\n",
    "            cr = 0\n",
    "            for j in range(10):\n",
    "                if u and j > v[i]:\n",
    "                    break\n",
    "                if mask >> j & 1:\n",
    "                    continue\n",
    "                if z and j == 0:\n",
    "                    cr += dp1(i + 1, 1, 0, 0)\n",
    "                else:\n",
    "                    cr += dp1(i + 1, 0, int(u == 1 and j == v[i]), mask | (1 << j))\n",
    "            return cr\n",
    "        res2 = int(n) - dp1(0, 1, 1, 0)\n",
    "        return res2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        l = len(n)\n",
    "        v = list(map(int, list(n)))\n",
    "        c = [0] * 10\n",
    "        @lru_cache(maxsize=1000000)\n",
    "        def dp(i, z, u, has, tc):\n",
    "            if i == l:\n",
    "                return has\n",
    "            cr = 0\n",
    "            for j in range(10):\n",
    "                if u and j > v[i]:\n",
    "                    break\n",
    "                if z and j == 0:\n",
    "                    cr += dp(i + 1, 1, 0, 0, tuple(c))\n",
    "                else:\n",
    "                    c[j] += 1\n",
    "                    cr += dp(i + 1, 0, int(u == 1 and j == v[i]), has | int(c[j] > 1), tuple(c))\n",
    "                    c[j] -= 1\n",
    "            return cr\n",
    "\n",
    "        # res1 = dp(0, 1, 1, 0, tuple(c))\n",
    "        @lru_cache(maxsize=1000000)\n",
    "        def dp1(i, z, u, mask):\n",
    "            if i == l:\n",
    "                return 1 ^ z\n",
    "            cr = 0\n",
    "            for j in range(10):\n",
    "                if u and j > v[i]:\n",
    "                    break\n",
    "                if mask >> j & 1:\n",
    "                    continue\n",
    "                if z and j == 0:\n",
    "                    cr += dp1(i + 1, 1, 0, 0)\n",
    "                else:\n",
    "                    cr += dp1(i + 1, 0, int(u == 1 and j == v[i]), mask | (1 << j))\n",
    "            return cr\n",
    "        res2 = int(n) - dp1(0, 1, 1, 0)\n",
    "        return res2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        from functools import lru_cache\n",
    "\n",
    "        ns = [0 for _ in range(0,10)]\n",
    "        idx = 9\n",
    "        while n>0:\n",
    "            n,mod = divmod(n,10)\n",
    "            ns[idx]=mod\n",
    "            idx-=1\n",
    "        # print(ns)\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def recur(i,stat,same,less,head):\n",
    "            # same&=  head\n",
    "            if i==9:\n",
    "                # print(bin(stat),same,less)\n",
    "                if not head:\n",
    "                    return 0\n",
    "                if same:\n",
    "                    if less:\n",
    "                        return 10\n",
    "                    else:\n",
    "                        return ns[i]+1\n",
    "                else:\n",
    "                    if less:\n",
    "                        return sum(1 if stat&(1<<j)>0 else 0 for j in range(0,10))\n",
    "                    else:\n",
    "                        return sum(1 if stat & (1 << j) > 0 else 0 for j in range(0, ns[i]+1))\n",
    "\n",
    "            if less:\n",
    "                return sum(recur(i+1,stat|(1<<j) if head or j>0 else 0,head and (same or ((stat&(1<<j))>0)),less,head or j>0) for j in range(0,10))\n",
    "            else:\n",
    "                tmp = recur(i+1,stat|(1<<ns[i]) if head or ns[i]>0 else 0, head and (same or ((stat&(1<<ns[i]))>0)),less,head or ns[i]>0)\n",
    "                tmp+=sum(recur(i+1,stat|(1<<j) if head or j>0 else 0,head and (same or ((stat&(1<<j))>0)),True,head or j>0) for j in range(0,ns[i]))\n",
    "                return tmp\n",
    "\n",
    "        return recur(0,0,False,False,False)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        matrix = list(map(int, str(n)))\n",
    "        length = len(matrix)\n",
    "\n",
    "        num_used = [False] * 10\n",
    "        @lru_cache(None)\n",
    "        def dfs(p, flag_max, flag_zero, num_used):\n",
    "            num_used = list(num_used)\n",
    "            ans = 0\n",
    "            upper = matrix[p] if flag_max else 9\n",
    "\n",
    "            if p == length - 1:\n",
    "                ans = upper + 1 - sum(num_used[:(upper + 1)])\n",
    "                return ans - 1 if flag_zero else ans\n",
    "\n",
    "            for u in range(upper+1):\n",
    "                if num_used[u]:\n",
    "                    continue\n",
    "\n",
    "                if u == 0 and flag_zero:\n",
    "                    ans += dfs(p+1, False, True, tuple(num_used))\n",
    "                elif u == upper and flag_max:\n",
    "                    num_used[u] = True\n",
    "                    ans += dfs(p+1, True, False, tuple(num_used))\n",
    "                    num_used[u] = False\n",
    "                else:\n",
    "                    num_used[u] = True\n",
    "                    ans += dfs(p+1, False, False, tuple(num_used))\n",
    "                    num_used[u] = False\n",
    "            return ans\n",
    "\n",
    "        ans = dfs(0, True, True, tuple(num_used))\n",
    "        return n - ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        digit = [int(d) for d in reversed(list(str(n)))]\n",
    "        length = len(digit)\n",
    "        dp = [[[[-1,-1] for k in range(2)] for j in range(1<<10)] for i in range(length)]\n",
    "\n",
    "        def dfs(idx: int, tight: bool, mask: int, lead: bool) -> int:\n",
    "            if idx < 0: return 1 if not lead else 0\n",
    "            if dp[idx][mask][tight][lead] != -1:\n",
    "                return dp[idx][mask][tight][lead]\n",
    "            ret, sup = 0, digit[idx] if tight else 9\n",
    "            for i in range(sup + 1):\n",
    "                if mask & (1 << i): continue\n",
    "                newLead = lead and i == 0\n",
    "                newMask = mask if newLead else mask | (1 << i)\n",
    "                ret += dfs(idx-1, tight and i == digit[idx], newMask, newLead)\n",
    "            dp[idx][mask][tight][lead] = ret\n",
    "            return ret\n",
    "\n",
    "        return n - dfs(length - 1, True, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        l=0\n",
    "        res=n\n",
    "        num=[0]*32\n",
    "        while n!=0:\n",
    "            l+=1\n",
    "            num[32-l]=n%10\n",
    "            n=(n//10)\n",
    "        dp=[[[0]*2 for _ in range(1024)] for __ in range(32)]\n",
    "        def dfs(idx,stat,bound):\n",
    "            nonlocal dp,num\n",
    "            if idx==32:\n",
    "                return 1 if stat!=0 else 0\n",
    "            if dp[idx][stat][bound]!=0:\n",
    "                return dp[idx][stat][bound]\n",
    "            tmp=0\n",
    "            if bound==1:\n",
    "                for i in range(0,num[idx]+1):\n",
    "                    if (stat&(1<<i))==0:\n",
    "                        ns=stat\n",
    "                        if stat!=0 or i>0:\n",
    "                            ns=(ns|(1<<i))\n",
    "                        tmp+=dfs(idx+1,ns,1 if i==num[idx] else 0)\n",
    "            else:\n",
    "                for i in range(0,10):\n",
    "                    if (stat&(1<<i))==0:\n",
    "                        ns=stat\n",
    "                        if stat!=0 or i>0:\n",
    "                            ns=(ns|(1<<i))\n",
    "                        tmp+=dfs(idx+1,ns,0)\n",
    "            dp[idx][stat][bound]=tmp\n",
    "            return tmp\n",
    "        \n",
    "        return res-dfs(0,0,1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        k = len(s)\n",
    "        @cache\n",
    "        def f(i, constrained,started, used):\n",
    "            used = list(used)\n",
    "            if i == k: return 1 if started else 0\n",
    "            ans = 0\n",
    "            M = 9 if not constrained else int(s[i])\n",
    "            L = 1 if not started else 0 #missed here\n",
    "            if not started:\n",
    "                ans = f(i+1, False, False, tuple(used))\n",
    "            for j in range(L,M+1):\n",
    "                if not used[j]:\n",
    "                    used[j] = True\n",
    "                    ans += f(i+1, constrained and j == M, True, tuple(used))\n",
    "                    used[j] = False\n",
    "            '''\n",
    "            if constrained:\n",
    "                used[M] = True\n",
    "                ans += f(i+1, True, True, tuple(used))\n",
    "                used[M] = False\n",
    "            '''\n",
    "            return ans \n",
    "        \n",
    "        return n-f(0, True, False,tuple([False]*10))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        num = str(n)\n",
    "        n = len(num)\n",
    "        @lru_cache(None)\n",
    "        def dfs(idx, bound, status):\n",
    "            if idx == n:\n",
    "                return status != 0\n",
    "            l = 0 \n",
    "            r = int(num[idx]) if bound & 2 else 9 \n",
    "            res = 0\n",
    "            for i in range(l, r + 1):\n",
    "                if i == 0 and status == 0:\n",
    "                    new_status = 0\n",
    "                elif status & 1 << i:\n",
    "                    continue \n",
    "                else:\n",
    "                    new_status = status | (1 << i)\n",
    "                new_bound = (l == i) | (i == r if bound & 2 else 0) << 1\n",
    "                res += dfs(idx + 1, new_bound, new_status)\n",
    "            return res  \n",
    "        return int(num) - dfs(0, 3, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        ln = len(s)\n",
    "        cache = {}\n",
    "\n",
    "        def dfs(index: int, limit: int, repeat: int, mask: int) -> int:\n",
    "            key = index << 13 | limit << 12 | repeat << 11 | mask\n",
    "            if key in cache:\n",
    "                return cache[key]\n",
    "            if index == ln:\n",
    "                # if repeat:\n",
    "                #     print(bin(mask), repeat)\n",
    "                return 1 if repeat else 0\n",
    "            up = (ord(s[index]) - ord('0')) if limit else 9\n",
    "            res = sum(dfs(index + 1, limit and i == up, mask != 0 and (repeat or (mask >> i) & 1 == 1),\n",
    "                          0 if mask == 0 and i == 0 else mask | (1 << i))\n",
    "                      for i in range(up + 1))\n",
    "\n",
    "            cache[key] = res\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 1, 0, 0)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        a = []\n",
    "        while n:\n",
    "            a.append(n%10)\n",
    "            n //=10\n",
    "    \n",
    "        @cache\n",
    "        def dfs(pos, status, limit, ok):\n",
    "            if pos < 0:\n",
    "                return ok == True           \n",
    "            ans = 0\n",
    "            up = a[pos] if limit else 9\n",
    "            for i in range(0, up+1):\n",
    "                if ok or (status != 1 and status>>i&1 == 1):\n",
    "                     ans += dfs(pos-1, status|(1<<i), limit and a[pos]==i, True)\n",
    "                elif pos == 0 and ((status == 0 or status == 1) or status>>i&1 == 0): # 对于不满足情况进行过滤，两种情况一直到最高位还是0，或者没有出现重复数字\n",
    "                    continue\n",
    "                elif i == 0 and (status == 0 or status == 1):\n",
    "                    ans += dfs(pos-1, status, limit and a[pos]==i, False) # 前导0, 还选0\n",
    "                else:\n",
    "                    ans += dfs(pos-1, status|(1<<i), limit and a[pos]==i, False) \n",
    "            return ans\n",
    "\n",
    "        return dfs(len(a)-1, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        def g(n):\n",
    "            s = str(n)\n",
    "            n = len(s)\n",
    "            @cache\n",
    "            def f(j, pre, havP, limit):\n",
    "                if j==n:\n",
    "                    return 1 \n",
    "                ans = 0\n",
    "                pre = set(pre)\n",
    "                b = {j for j in range(10) if j not in pre}\n",
    "                if havP==0:\n",
    "                    ans += f(j+1, tuple(pre), 0, 0)\n",
    "                    b.remove(0)\n",
    "                c = int(s[j]) if limit else 9\n",
    "                for k in b:\n",
    "                    if k<=c:\n",
    "                        np = tuple([k] + list(pre))\n",
    "                        ans += f(j+1, np, 1, limit&(k==c))\n",
    "                return ans \n",
    "            return f(0, tuple([]), 0, 1)\n",
    "        return n - (g(n) - 1)\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @lru_cache(None) # 记忆化搜索\n",
    "        def dp(i: int,vis: int,has: bool,is_num: bool,is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(has)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = dp(i+1,0,False,False,False)\n",
    "            low = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for k in range(low,up+1):\n",
    "                res += dp(i+1,vis^(1<<k),has or vis>>k&1,True,is_limit and k == up)\n",
    "            return res\n",
    "        return dp(0,0,False,False,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @lru_cache(None)\n",
    "        def dp(i: int,vis: int,has: bool,is_num: bool,is_limit: bool) -> int:\n",
    "            if i == len(s):\n",
    "                return int(has)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = dp(i+1,0,False,False,False)\n",
    "            low = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for k in range(low,up+1):\n",
    "                res += dp(i+1,vis^(1<<k),has or vis>>k&1,True,is_limit and k == up)\n",
    "            return res\n",
    "        return dp(0,0,False,False,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        def f(i:int,mask:int,isLimit:bool,isNum:bool)->int:\n",
    "\n",
    "            if i == l:\n",
    "                if isNum:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "           \n",
    "            if not isLimit and isNum and m[i][mask]!=-1:\n",
    "                return m[i][mask]\n",
    "\n",
    "            down = 0 if isNum else 1\n",
    "            up = int(s[i]) if isLimit else 9\n",
    "\n",
    "           \n",
    "\n",
    "            res = 0 if isNum else f(i+1,mask,False,False)\n",
    "            for d in range(down,up+1):\n",
    "                if (mask>>d)&1==0:\n",
    "                    res+=f(i+1,mask|(1<<d),isLimit and d ==up,True)\n",
    "            \n",
    "            if not isLimit and isNum: m[i][mask] = res;\n",
    "            return res\n",
    "\n",
    "        s = list(str(n))\n",
    "        l = len(s)\n",
    "        m = -np.ones((l,1024))\n",
    "        \n",
    "        return int(n - f(0,0,True,False))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        n = [int(x) for x in str(n)]\n",
    "\n",
    "        def get_bit(mask, p):\n",
    "            return (mask >> p) & 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(p, zero_trail, limit, mask, choice_limit):\n",
    "            ans = 0\n",
    "            if p == len(n):\n",
    "                return 1 - int(choice_limit)\n",
    "            for digit in range(10):\n",
    "                if digit > n[p]:\n",
    "                    if limit:\n",
    "                        continue\n",
    "                    new_choice_limit = choice_limit and get_bit(mask, digit) == 0\n",
    "                    if new_choice_limit:\n",
    "                        new_mask = mask + (1 << digit)\n",
    "                    else:\n",
    "                        new_mask = mask\n",
    "                    ans += dfs(p + 1, False, limit, new_mask, new_choice_limit)\n",
    "                else:\n",
    "                    new_limit = limit and digit == n[p]\n",
    "                    new_zero_trail = zero_trail and digit == 0\n",
    "                    if new_zero_trail:\n",
    "                        ans += dfs(p + 1, new_zero_trail, new_limit, mask, choice_limit)\n",
    "                        continue\n",
    "                    new_choice_limit = choice_limit and get_bit(mask, digit) == 0\n",
    "                    if new_choice_limit:\n",
    "                        new_mask = mask + (1 << digit)\n",
    "                    else:\n",
    "                        new_mask = mask\n",
    "                    ans += dfs(p + 1, new_zero_trail, new_limit, new_mask, new_choice_limit)\n",
    "            return ans\n",
    "\n",
    "        return dfs(0, 1, 1, 0, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        NUM = list(map(int, str(n)))\n",
    "        L = len(NUM)\n",
    "        # i位、上一位为否最高了、当前mask、是否重复了\n",
    "        @cache\n",
    "        def find(idx, tight, mask, dup):\n",
    "            if idx >= L:\n",
    "                return 1 if dup else 0\n",
    "            ans = 0\n",
    "            r = NUM[idx] if tight else 9\n",
    "            for i in range(r + 1):\n",
    "                if (mask == 0 and i == 0) or dup:\n",
    "                    next_mask = 0\n",
    "                    next_dup = dup\n",
    "                else:\n",
    "                    if mask & (1 << i) > 0:\n",
    "                        next_dup = True\n",
    "                        next_mask = mask\n",
    "                    else:\n",
    "                        next_mask = mask ^ (1 << i)\n",
    "                        next_dup = dup\n",
    "                next_tight = True if (tight and i == NUM[idx]) else False\n",
    "                ans += find(idx + 1, next_tight, next_mask, next_dup)\n",
    "            return ans\n",
    "\n",
    "        return find(0, True, 0, False)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        self.nums = str(n)\n",
    "        return n - self.dfs(0,0,True,False)\n",
    "   \n",
    "    @cache\n",
    "    def dfs(self,i: int, mask: int, isLimit: bool, isNum: bool) -> int:\n",
    "        if i == len(self.nums):\n",
    "            return int(isNum)\n",
    "        res = 0\n",
    "        if not isNum:\n",
    "            res = self.dfs(i+1,mask,False,False)\n",
    "        low = 0 if isNum else 1\n",
    "        up = int(self.nums[i]) if isLimit else 9\n",
    "        for d in range(low, up + 1):\n",
    "            if (mask & (1 << d)) == 0:\n",
    "                res += self.dfs(i+1,mask | (1 << d), isLimit and d==up, True)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "\n",
    "        @cache\n",
    "        def f(i,mask,is_target,is_limit,is_num):\n",
    "            if i == len(s): return int(is_target)\n",
    "            res = 0 if is_num else f(i+1,0,False,False,False)\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            low = 0 if is_num else 1\n",
    "            for d in range(low,up+1):\n",
    "                new_is_target = bool(mask&(1<<d)) or is_target\n",
    "                res += f(i+1,mask|(1<<d),new_is_target,is_limit and d == up,True)\n",
    "            return res\n",
    "\n",
    "        return f(0,0,False,True,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import perm\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        x = len(str(n))\n",
    "        if x == 1:\n",
    "            return 0\n",
    "        @cache\n",
    "        def f(i,preSame,pres,repeated):\n",
    "            if i==x:\n",
    "                if repeated:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            # 从第一个开始看\n",
    "            # 若前面都是0\n",
    "            current = int(str(n)[i])\n",
    "            if preSame:\n",
    "                limit = current\n",
    "            else:\n",
    "                limit = 9\n",
    "            # 当前第i位可以填充的数字\n",
    "            res = 0\n",
    "            for k in range(limit+1):\n",
    "                # 已经重复了\n",
    "                if repeated:\n",
    "                    newRepeated = True\n",
    "                elif pres & (1<<k):\n",
    "                    newRepeated = True\n",
    "                else:\n",
    "                    newRepeated = False\n",
    "                newPreSame = preSame & (k == current)\n",
    "                if k == 0 and pres == 0:\n",
    "                    newPres = 0\n",
    "                else:\n",
    "                    newPres = pres | (1<<k)\n",
    "                res += f(i+1,newPreSame,newPres,newRepeated)\n",
    "            return res\n",
    "        return f(0,True,0,False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        num = str(n)\n",
    "        l = len(num)\n",
    "\n",
    "        @cache\n",
    "        def f(i, mask, is_limit, is_num, cnt):\n",
    "            if i == l:\n",
    "                return cnt if is_num else 0\n",
    "            \n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res += f(i + 1, mask, False, is_num, 0)\n",
    "\n",
    "            down = 0 if is_num else 1\n",
    "            up = int(num[i]) if is_limit else 10\n",
    "            for k in range(down, up):\n",
    "                res += f(i + 1, (mask|(1<<k)), False, True, int((mask&(1<<k))>0)|cnt)\n",
    "            if is_limit:\n",
    "                res += f(i + 1, (mask|(1<<up)), True, True, int((mask&(1<<up))>0)|cnt)\n",
    "            return res\n",
    "\n",
    "        return f(0, 0, True, False, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def dfs(i, flag, limit, rep):\n",
    "            if i == len(s):\n",
    "                return rep\n",
    "            res = 0\n",
    "            up = int(s[i]) if limit else 9\n",
    "            for d in range(up+1):\n",
    "                res += dfs(i+1, flag | 1<<d if flag>0 or d>0 else 0, limit and d == up, rep or bool(flag & (1<<d)))\n",
    "            return res\n",
    "        return dfs(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        return n - self.f(0, 0, True, False, s)\n",
    "    \n",
    "    @cache\n",
    "    def f(self, i: int, mask: int, is_limit: bool, is_num: bool, s: str):\n",
    "        if i == len(s):\n",
    "            return int(is_num)\n",
    "        res = 0\n",
    "        if not is_num:\n",
    "            res = self.f(i + 1, mask, False, False, s)\n",
    "        low = 0 if is_num else 1\n",
    "        up = int(s[i]) if is_limit else 9\n",
    "        for d in range(low, up + 1):\n",
    "            if (mask >> d & 1) == 0:\n",
    "                res += self.f(i + 1, mask | (1 << d), is_limit and d == up, True, s)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        return n - self.f(0, 0, True, False, s)\n",
    "\n",
    "    @cache\n",
    "    def f(self, i: int, mask: int, is_limit: bool, is_num: bool, s: str):\n",
    "        if i == len(s):\n",
    "            return int(is_num)\n",
    "        \n",
    "        res = 0\n",
    "        if not is_num:\n",
    "            res = self.f(i + 1, mask, False, False, s)\n",
    "        \n",
    "        low = 0 if is_num else 1\n",
    "        up = int(s[i]) if is_limit else 9\n",
    "\n",
    "        for d in range(low, up + 1):\n",
    "            if (mask >> d & 1) == 0:\n",
    "                res += self.f(i + 1, mask | (1 << d), is_limit and d == up, True, s)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "class Solution:\n",
    "    @lru_cache(None)\n",
    "    def unique(self, s, can=(0,1,2,3,4,5,6,7,8,9), zero=True):\n",
    "        if len(s) == 1:\n",
    "            res = 0\n",
    "            for c in can:\n",
    "                if zero and c == 0:\n",
    "                    continue\n",
    "                if c <= int(s):\n",
    "                    res += 1\n",
    "            return res\n",
    "        res = 0\n",
    "        first = int(s[0])\n",
    "        for f in range(0, first):\n",
    "            if f not in can:\n",
    "                continue\n",
    "            if f or not zero:\n",
    "                res += self.unique(\"9\"*(len(s)-1), tuple([c for c in can if c != f]), False)\n",
    "            else:\n",
    "                res += self.unique(\"9\"*(len(s)-1), can, True)\n",
    "        if first in can:\n",
    "            if first == 0 and zero:\n",
    "                res += self.unique(s[1:], can, True)\n",
    "            else:\n",
    "                res += self.unique(s[1:], tuple([c for c in can if c != first]), False)\n",
    "        return res\n",
    "    \n",
    "    def numDupDigitsAtMostN(self, N: int) -> int:\n",
    "        return N-self.unique(str(N))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from scipy.special import comb as s_comb\n",
    "from scipy.special import perm as s_perm\n",
    "\n",
    "\n",
    "def comb(a, b):\n",
    "    return int(s_comb(a, b))\n",
    "\n",
    "\n",
    "def perm(a, b):\n",
    "    return int(s_perm(a, b))\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, N):\n",
    "        limit, s = list(map(int, str(N + 1))), set()\n",
    "        n, res = len(limit), sum(9 * perm(9, i) for i in range(len(limit) - 1))\n",
    "        for i, x in enumerate(limit):\n",
    "            for y in range(i == 0, x):\n",
    "                if y not in s:\n",
    "                    res += perm(9 - i, n - i - 1)\n",
    "            if x in s:\n",
    "                break\n",
    "            s.add(x)\n",
    "        return N - res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        if len(n)<=1:return 0\n",
    "        #先计算长度不同的时候,比如之前为“98782”，我们考虑长度为1，2，3，4的全部符合条件的不重复的数字之和。\n",
    "        #最大的长度\n",
    "        limit=len(n)-1\n",
    "        #遍历长度\n",
    "        part1=0\n",
    "        for i in range(1,limit+1):\n",
    "            if i==1:\n",
    "                part1+=10\n",
    "            else:\n",
    "                #第一个数有9中可能，第二个也是9中，第三个是8中\n",
    "                pre=9\n",
    "                i-=1\n",
    "                temp=9\n",
    "                for j in range(i,0,-1):\n",
    "                    pre*=temp\n",
    "                    temp-=1\n",
    "                part1+=pre\n",
    "        # 长度相同，并且第一位取不同的值，比如第一位是5，那么就可以取1，2，3，4，后面的数就可以随意取值\n",
    "        part2=0\n",
    "        pre = 1\n",
    "        temp = 9\n",
    "        for j in range(limit, 0, -1):\n",
    "            pre *= temp\n",
    "            temp -= 1\n",
    "        part2 += pre*(int(n[0])-1)\n",
    "        # 长度相同并且第一位取相同值,比如之前是9876，现在第一位取9，后面的3位数\n",
    "        temp=n[1:]\n",
    "        #遍历每一个位置\n",
    "        pre=[n[0]]\n",
    "        for i in range(len(n[1:])):\n",
    "            cur=temp[i]\n",
    "            new=[]\n",
    "            for j in range(10):\n",
    "                for k in pre:\n",
    "                    if str(j) not in k and int(k+str(j))<=int(n[:len(k+str(j))]):\n",
    "                        new.append(k+str(j))\n",
    "            pre=new    \n",
    "        part3=len(pre)\n",
    "        ans=int(n)-part1-part2-part3\n",
    "        if set(list(n)) != len(n):\n",
    "            ans+=1\n",
    "            \n",
    "        return ans\n",
    "\n",
    "# class Solution:\n",
    "#     def numDupDigitsAtMostN(self, N: int) -> int:\n",
    "#         if N <= 10:  return 0\n",
    "#         x = [1]\n",
    "#         for i in range(10):  # x[i] = i!\n",
    "#             x.append(x[-1] * (i + 1))\n",
    "#         m = len(str(N))\n",
    "#         logits = list(map(int, str(N)))\n",
    "#         count = 0  # 无重复数字的个数\n",
    "#         # 1. 1<=length<m\n",
    "#         for i in range(1, m):  # 9*A(9, i-1) for all 1<=i<m\n",
    "#             count += 9 * x[9] // x[10 - i]\n",
    "#         # 2. length==m\n",
    "#         count += (logits[0] - 1) * x[9] // x[10 - m]  # case 0: 1<=a[0]<logits[0]\n",
    "#         for i in range(1, m):  # case i: a[k]==logits[k] for all 0<=k<i\n",
    "#             for j in range(logits[i]):  # select a[i]<logits[i] and a[i]!=a[k] for all 0<=k<i\n",
    "#                 if j not in logits[:i]:\n",
    "#                     count += x[9 - i] // x[10 - m]\n",
    "#             if logits[i] in logits[:i]:  # let a[i]=logits[i]\n",
    "#                 break\n",
    "#         if i == m - 1 and logits[m - 1] not in logits[:m - 1]:\n",
    "#             count += 1\n",
    "#         return N - count\n",
    "#\n",
    "#\n",
    "# 作者：Gorilla\n",
    "# 链接：https: // leetcode - cn.com / problems / numbers -\n",
    "# with-repeated - digits / solution / python3qiu - wu - zhong - fu - shu - zi - de - ge - shu - by - gorilla /\n",
    "#     来源：力扣（LeetCode）\n",
    "#     著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s = str(n)\n",
    "        @cache\n",
    "        def f(i: int,diff: int,flag: bool,is_num: bool,is_limit: bool)->int:\n",
    "            if i == len(s):\n",
    "                return int(flag)\n",
    "            res = 0\n",
    "            if not is_num:\n",
    "                res = f(i+1,diff,False,False,False)\n",
    "            d0 = 0 if is_num else 1\n",
    "            up = int(s[i]) if is_limit else 9\n",
    "            for val in range(d0,up+1):\n",
    "                res += f(i+1,diff + (1<<val),flag or ((diff>>val)&1)==1,True,is_limit and val == up)\n",
    "            return res\n",
    "        return f(0,0,False,False,True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        def dfs(i, mask, isLimit, hasDup):\n",
    "            if i == len(s):\n",
    "                return 1 if hasDup else 0\n",
    "            if(i, mask, isLimit, hasDup) in hashMap:\n",
    "                return hashMap[(i, mask, isLimit, hasDup)]\n",
    "            up = int(s[i]) if isLimit else 9\n",
    "            res = 0\n",
    "            for d in range(up+1):\n",
    "                mask1 = mask if (mask == 0 and d == 0) else mask | (1 << d)\n",
    "                hasDup1 = hasDup or (mask & (1 << d))\n",
    "                res += dfs(i+1, mask1, isLimit and (d == up), hasDup1)\n",
    "            hashMap[(i, mask, isLimit, hasDup)] = res\n",
    "            return res\n",
    "\n",
    "        s = str(n)\n",
    "        hashMap = {}\n",
    "        return dfs(0, 0, True, False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        N = len(str(n))\n",
    "        digits = list(str(n))\n",
    "        digits = [int(d) for d in digits]\n",
    "\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(cur: int, num_digit: int, mask: int, is_limited: bool):\n",
    "            # 已遍历了N个数位，已填入了num_digit个数字，使用数字的情况为mask\n",
    "            if cur == N:\n",
    "                # 如果使用的数字数量比填入的数字少，说明肯定有重复的数字，成功一次，返回1，否则每一位都不同，返回0\n",
    "                if mask.bit_count() < num_digit:\n",
    "                    return 1\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            # 如果之前没有填入过数字，可以继续不填入，那么显然mask=0，is_limited=False\n",
    "            if num_digit == 0:\n",
    "                res += dfs(cur + 1, 0, 0, False)\n",
    "\n",
    "            upper = digits[cur] if is_limited else 9\n",
    "            lower = 0 if num_digit else 1\n",
    "\n",
    "            for i in range(lower, upper + 1):\n",
    "                res += dfs(cur + 1, num_digit + 1, mask | (1 << i), is_limited & (i == upper))\n",
    "\n",
    "            return res\n",
    "\n",
    "        return dfs(0, 0, 0, True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 2376 (357的promax版, 体现在需要添加limit标记)\n",
    "    # ! 同257一样, 需要在前导零的环境下特殊考虑\n",
    "    def countSpecialNumbers(self, n: int) -> int:\n",
    "        def memoryDFS(pos:int, pre:int, limit:bool, lead:bool, sta:int):\n",
    "            if pos == len(self.digit):\n",
    "                if lead: return 0\n",
    "                else: return 1\n",
    "            state = ' '.join([str(pos), str(pre), str(sta)])\n",
    "            if not limit and not lead and state in self.memory:\n",
    "                return self.memory[state]\n",
    "            upbound = self.digit[pos] + 1 if limit else 10\n",
    "            res = 0\n",
    "            for cur in range(upbound):\n",
    "                if lead and cur == 0: res += memoryDFS(pos+1, cur, False, True, sta)\n",
    "                else:\n",
    "                    if (1<<cur) & sta: continue\n",
    "                    res += memoryDFS(pos+1, cur, limit and cur==self.digit[pos], lead and cur==0, sta | (1<<cur))\n",
    "            if not limit and not lead: self.memory[state] = res \n",
    "            return res\n",
    "        self.memory = {}\n",
    "        self.digit = [int(ni) for ni in str(n)]\n",
    "        return memoryDFS(0, 0, True, True, 0)\n",
    "    # 1012 (357的互逆题)\n",
    "    # ! 直接做也不难, 也可以用互逆思想: 至少一位重复 = 所有数 - 每位都不重复.\n",
    "    # ! 互逆思想的代码:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        return n - self.countSpecialNumbers(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        s=str(n)\n",
    "        @cache\n",
    "        def dfs(i,mask,is_limit,is_num,ans):\n",
    "            if i==len(s):\n",
    "                return ans>=1\n",
    "        \n",
    "            \n",
    "            res=0\n",
    "            if not is_num:\n",
    "                res+=dfs(i+1,mask,False,False,0)\n",
    "            \n",
    "            up=int(s[i]) if is_limit else 9\n",
    "            for j in range(1-is_num,up+1):\n",
    "                if mask>>j&1==0:\n",
    "                    res+=dfs(i+1,mask|(1<<j),is_limit and j==up,True,ans)\n",
    "                else:\n",
    "                    res+=dfs(i+1,mask,is_limit and j==up,True,ans+1)\n",
    "            return res\n",
    "\n",
    "        return dfs(0,0,True,False,0)\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numDupDigitsAtMostN(self, n: int) -> int:\n",
    "        n = str(n)\n",
    "        l = len(n)\n",
    "        v = list(map(int, list(n)))\n",
    "        c = [0] * 10\n",
    "        @lru_cache(maxsize=100000)\n",
    "        def dp(i, z, u, has, tc):\n",
    "            if i == l:\n",
    "                return has\n",
    "            cr = 0\n",
    "            for j in range(10):\n",
    "                if u and j > v[i]:\n",
    "                    break\n",
    "                if z and j == 0:\n",
    "                    cr += dp(i + 1, 1, 0, 0, tuple(c))\n",
    "                else:\n",
    "                    c[j] += 1\n",
    "                    cr += dp(i + 1, 0, int(u == 1 and j == v[i]), has | int(c[j] > 1), tuple(c))\n",
    "                    c[j] -= 1\n",
    "            return cr\n",
    "        return dp(0, 1, 1, 0, tuple(c))\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
